package com.demo.堆;

import com.demo.排序算法.test.Sort;

public class Heap {

    // 大根堆构造
    // index 为当前节点的下标
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1)/2]) {
            Sort.swap(arr, index, (index - 1)/2);
            index = (index - 1)/2;
        }
    }

    // 某个树在index 位置能否向下移动
    // heapSize 左右孩子是否越界
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int max = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            max = arr[max] > arr[index] ? max : index;
            if (max == index) {
                break;
            }
            Sort.swap(arr, index, max);
            index = max;
            left = index * 2 + 1;
        }
    }
}
